|
In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond 1-for-1 to the positive rational numbers. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction ''a''/''b'' has as its two children the numbers ''a''/(''a'' + ''b'') and (''a'' + ''b'')/''b''. Every positive rational number appears exactly once in the tree. The sequence of rational numbers in a breadth-first traversal of the Calkin–Wilf tree is known as the Calkin–Wilf sequence. Its sequence of numerators (or, offset by one, denominators) is Stern's diatomic series, and can be computed by the fusc function. The Calkin–Wilf tree is named after Neil Calkin and Herbert Wilf, who considered it in their 2000 paper. The tree was introduced earlier by Jean Berstel and Aldo de Luca〔, Section 6.〕 as ''Raney tree'', since they drew some ideas from a paper by George N. Raney.〔.〕 Stern's diatomic series was formulated much earlier by Moritz Abraham Stern, a 19th-century German mathematician who also invented the closely related Stern–Brocot tree. ==Definition and structure== The Calkin–Wilf tree may be defined as a directed graph in which each positive rational number ''a''/''b'' occurs as a vertex and has one outgoing edge to another vertex, its parent. We assume that ''a''/''b'' is in simplest terms; that is, the greatest common divisor of ''a'' and ''b'' is 1. If ''a''/''b'' < 1, the parent of ''a''/''b'' is ''a''/(''b'' − ''a''); if ''a''/''b'' is greater than one, the parent of ''a''/''b'' is (''a'' − ''b'')/''b''. Thus, in either case, the parent is a fraction with a smaller sum of numerator and denominator, so repeated reduction of this type must eventually reach the number 1. As a graph with one outgoing edge per vertex and one root reachable by all other vertices, the Calkin–Wilf tree must indeed be a tree. The children of any vertex in the Calkin–Wilf tree may be computed by inverting the formula for the parents of a vertex. Each vertex ''a''/''b'' has one child whose value is less than 1, ''a''/(''a'' + ''b''), because this is the only value less than 1 whose parent formula leads back to ''a''/''b''. Similarly, each vertex ''a''/''b'' has one child whose value is greater than 1, (''a'' + ''b'')/''b''.〔The description here is dual to the original definition by Calkin and Wilf, which begins by defining the child relationship and derives the parent relationship as part of a proof that every rational appears once in the tree. As defined here, every rational appears once by definition, and instead the fact that the resulting structure is a tree requires a proof.〕 Although it is a binary tree (each vertex has two children), the Calkin–Wilf tree is not a binary search tree: its inorder does not coincide with the sorted order of its vertices. However, it is closely related to a different binary search tree on the same set of vertices, the Stern–Brocot tree: the vertices at each level of the two trees coincide, and are related to each other by a bit-reversal permutation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Calkin–Wilf tree」の詳細全文を読む スポンサード リンク
|